/*
 * Copyright (C) 2012 Richard Schilling
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package dalvik.vm.analysis;

import static dalvik.vm.analysis.CodeVerifyConstants.*;
import static dalvik.vm.analysis.RegisterType.*;

import java.util.BitSet;
import java.util.LinkedList;

import com.android.dx.io.ClassData.Method;
import com.android.dx.io.ClassDef;
import com.android.dx.io.Code;
import com.android.dx.io.DexBuffer;
import com.android.dx.io.Opcodes;
import com.android.dx.io.instructions.DecodedInstruction;

import dalvik.vm.analysis.AnalyzableInstruction.RegisterLine;
import dalvik.vm.analysis.InstructionList.RegisterTable;
import dalvik.vm.util.SparseArray;

/**
 * An implementation of the CodeVerify.cpp module in Java. This module is found
 * in the Dalvik VM and is used to verify code that is loaded into the VM. Any
 * code we touch needs to pass the tests in CodeVerify.cpp and, ergo, this file
 * as well.
 * <p>
 * This is as much of a direct port of the logic as possible.
 * <p>
 * Other projects have tried to do something similar (e.g. smali), but I think
 * the approach found in the .cpp module is a little more straightforward.
 * <p>
 * This class operates on objects defined in com.android.dx.io because it's
 * assumed that the class data to verify is already placed in a DEX file.
 * 
 * @author rschilling
 */
public abstract class CodeVerify {

    /**
     * The buffer that the code comes from.
     */
    private DexBuffer buffer;

    public CodeVerify(DexBuffer buffer) {

        if (buffer == null)
            throw new IllegalArgumentException("buffer cannot be null.");

        this.buffer = buffer;
    }

    /**
     * RegType holds information about the type of data held in a register. For
     * most types it's a simple enum. For reference types it holds a pointer to
     * the ClassObject, and for uninitialized references it holds an index into
     * the UninitInstanceMap.
     */
    public static class RegType {

        public RegisterType register;
        public ClassDef classObject;
        public int unititialized = Integer.MIN_VALUE;

        /**
         * determine if "type" is actually an object reference
         * (init/uninit/zero)
         */
        public boolean regTypeIsReference() {
            return (register.asInt() > kRegTypeMAX.asInt() || register == kRegTypeUninit || register == kRegTypeZero);
        }

        /** determine if "type" is an uninitialized object reference */
        public boolean regTypeIsUninitReference() {
            return ((register.asInt() & kRegTypeUninitMask) == RegisterType.kRegTypeUninit.asInt());
        }

        /**
         * convert the initialized reference "type" to a ClassObject pointer.
         * (does not expect uninit ref types or "zero")
         */
        public ClassDef regTypeInitializedReferenceToClass() {
            if (regTypeIsReference() && register != kRegTypeZero)
                throw new IllegalStateException(
                        "this is a reference type but the register type is not zero.");

            if ((register.asInt() & 0x01) == 0) {
                return classObject;
            } else {
                // LOG_VFY("VFY: attempted to use uninitialized reference");
                return null;
            }
        }

        /** extract the index into the uninitialized instance map table */
        public int regTypeToUninitIndex() {
            if (!regTypeIsUninitReference())
                throw new IllegalStateException(
                        "this register type does not have an associated class reference.");

            return (register.asInt() & ~kRegTypeUninitMask) >> kRegTypeUninitShift;
        }
        
        
    }

    /**
     * Table that maps uninitialized instances to classes, based on the address
     * of the new-instance instruction. One per method.
     * <p>
     * The integer is the code offset, or -1 for method ara ("this").
     * <p>
     * The object is the class created at that address.
     */
    public SparseArray<ClassDef> UninitInstanceMap = new SparseArray<ClassDef>();

    /*
     * InsnFlags is a 32-bit integer with the following layout: 0-15 instruction
     * length (or 0 if this address doesn't hold an opcode) 16-31 single bit
     * flags: InTry: in "try" block; exceptions thrown here may be caught
     * locally BranchTarget: other instructions can branch to this instruction
     * GcPoint: this instruction is a GC safe point Visited: verifier has
     * examined this instruction at least once Changed: set/cleared as bytecode
     * verifier runs
     */
    // typedef u4 InsnFlags;

    /**
     * Various bits of data used by the verifier and register map generator.
     */
    public static final class VerifierData {

        /*
         * The method we're working on.
         */
        public Method method;

        /*
         * Number of code units of instructions in the method. A cache of the
         * value calculated by dvmGetMethodInsnsSize().
         */
        public int insnsSize;

        /*
         * Number of registers we track for each instruction. This is equal to
         * the method's declared "registersSize". (Does not include the pending
         * return value.)
         */
        public int insnRegCount;

        /**
         * AnalyzableInstruction widths and flags, one entry per code unit.
         * <p>
         * InsnFlags is a 32-bit integer with the following layout: 0-15
         * instruction length (or 0 if this address doesn't hold an opcode)
         * 16-31 single bit flags: InTry: in "try" block; exceptions thrown here
         * may be caught locally BranchTarget: other instructions can branch to
         * this instruction GcPoint: this instruction is a GC safe point
         * Visited: verifier has examined this instruction at least once
         * Changed: set/cleared as bytecode verifier runs
         */
        int[] insnFlags;

        /*
         * Uninitialized instance map, used for tracking the movement of objects
         * that have been allocated but not initialized.
         */
        SparseArray<ClassDef> uninitMap = new SparseArray<ClassDef>();

        /**
         * Array of RegisterLine structs, one entry per code unit. We only need
         * entries for code units that hold the start of an "interesting"
         * instruction. For register map generation, we're only interested in GC
         * points.
         */
        LinkedList<RegisterLine> registerLines = new LinkedList<RegisterLine>();

        /*
         * The number of occurrences of specific opcodes.
         */
        int newInstanceCount;
        int monitorEnterCount;

        /*
         * Array of pointers to basic blocks, one entry per code unit. Used for
         * liveness analysis.
         */
        public VfyBasicBlock basicBlocks;
    };

    /**
     * Basic code blocks
     * 
     * @author rschilling
     */
    public static class VfyBasicBlock {

        int firstAddr; /* address of first instruction */
        int lastAddr; /* address of last instruction */
        PointerSet predecessors = new PointerSet(); /*
                                                     * set of basic blocks that
                                                     * can flow here
                                                     */
        BitSet liveRegs = new BitSet(); /* liveness for each register */
        boolean changed; /* input set has changed, must re-eval */
        boolean visited; /* block has been visited at least once */

    }

    /**
     * Sorted, expanding list of pointers.
     */
    public static class PointerSet extends LinkedList<Object> {};

    /**
     * Create a new uninitialized instance map. The sparse array indexes are
     * set to address values within the method where a new instance is created.
     * The values of the sparse array are filled in elsewhere.
     * <p>
     * The map is allocated and populated with address entries. The addresses
     * appear in ascending order to allow binary searching.
     * <p>
     * Very few methods have 10 or more new-instance instructions; the majority
     * have 0 or 1. Occasionally a static initializer will have 200+.
     * <p>
     * TODO: merge this into the static pass or initRegisterTable; want to avoid
     * walking through the instructions yet again just to set up this table
     */
    SparseArray<ClassDef> dvmCreateUninitInstanceMap(Method meth, int[] insnFlags,
            int newInstanceCount) {

        if (meth.getCodeOffset() == 0)
            return null; // original logic returns null if something is wrong.

        SparseArray<ClassDef> uninitMap = new SparseArray<ClassDef>();

        if (isInitMethod(meth))
            uninitMap.put(kUninitThisArgAddr, null);

        Code code = buffer.readCode(meth);
        DecodedInstruction[] decodedInstructions = DecodedInstruction.decodeAll(code
                .getInstructions());
        for (int i = 0; i < decodedInstructions.length; i++) {
            if (decodedInstructions[i] == null)
                continue;

            if (decodedInstructions[i].getOpcode() == Opcodes.NEW_INSTANCE
                    || decodedInstructions[i].getOpcode() == Opcodes.NEW_INSTANCE_JUMBO)
                uninitMap.put(i, null);

        }

        return uninitMap;
    }

    /*
     * Release the storage associated with an UninitInstanceMap.
     */
    void dvmFreeUninitInstanceMap(SparseArray<ClassDef> uninitMap) {
        uninitMap.clear();
    }

    /*
     * Set the class object associated with the instruction at "addr".
     * 
     * Returns the map slot index, or -1 if the address isn't listed in the map
     * (shouldn't happen) or if a class is already associated with the address
     * (bad bytecode).
     * 
     * Entries, once set, do not change -- a given address can only allocate
     * one type of object.
     */
    static int setUninitInstance(SparseArray<ClassDef> uninitMap, int addr, ClassDef clazz) {

        if (uninitMap.indexOfKey(addr) < 0) {
            dvmLogVerifyFailure(null, "VFY: addr %d not found in uninit map",
                    Integer.toString(addr));
            return -1;
        }

        if (uninitMap.get(addr) != null) {
            dvmLogVerifyFailure(null, "VFY: addr %d already set to %p, not setting to %p",
                    Integer.toString(addr), uninitMap.get(addr).toString(), clazz.toString());
            return -1;
        }

        uninitMap.put(addr, clazz);
        return uninitMap.indexOfKey(addr);

    }

    /**
     * Get the class object at the specified index. Strictly speaking, this
     * function is not necessary, but it's kept here to maintain a parity with
     * the C++ version.
     */
    static ClassDef getUninitInstance(SparseArray<ClassDef> uninitMap, int idx) {
        return uninitMap.valueAt(idx);
    }

    /**
     * Output a code verifier warning message. For the pre-verifier it's not
     * a big deal if something fails (and it may even be expected), but if
     * we're doing just-in-time verification it's significant. Method passed may
     * be null.
     */
    static void dvmLogVerifyFailure(Method meth, String... format) {
        String[] s = new String[format.length - 1];
        System.arraycopy(format, 1, s, 0, format.length - 1);

        // TDOO use a proper logger.
        System.out.println(String.format(format[0], s));

    }

    /*
     * Verify bytecode in "meth". "insnFlags" should be populated with
     * instruction widths and "in try" flags.
     */
    boolean dvmVerifyCodeFlow(VerifierData[] vdata) {
        throw new UnsupportedOperationException("TODO must be implemented");

    }

    public boolean isInitMethod(Method meth) {
        throw new UnsupportedOperationException("TODO must be implemented");
    }

    public RegType getInvocationThis(RegisterLine registerLine, DecodedInstruction pDecInsn,
            VerifyError pFailure) {
        throw new UnsupportedOperationException("TODO must be implemented");

    }

    static void verifyRegisterType(RegisterLine registerLine, int vsrc, RegType checkType,
            VerifyError pFailure) {
        throw new UnsupportedOperationException("TODO must be implemented");
    }

    public boolean doCodeVerification(VerifierData vdata, RegisterTable regTable) {
        throw new UnsupportedOperationException("TODO must be implemented");
    }

    public boolean verifyInstruction(Method meth, int[] insnFlags, RegisterTable regTable,
            int insnIdx, SparseArray<ClassDef> uninitMap, int pStartGuess) {
        throw new UnsupportedOperationException("TODO must be implemented");
    }

    public ClassDef findCommonSuperclass(ClassDef c1, ClassDef c2) {
        throw new UnsupportedOperationException("TODO must be implemented");
    }

    static void dumpRegTypes(VerifierData vdata, RegisterLine registerLine, int addr,
            String addrName, SparseArray<ClassDef> uninitMap, int displayFlags) {
        throw new UnsupportedOperationException("TODO must be implemented");
    }
    
    /** convert the reference "type" to a ClassObject pointer */
    static ClassDef regTypeReferenceToClass(RegType type,
            SparseArray<ClassDef> uninitMap)
    {
        if (type.regTypeIsReference() && type.register != kRegTypeZero)
            throw new IllegalStateException("type is a reference type but the register type is not zero");
        
        if (type.regTypeIsUninitReference()) {
            if (uninitMap == null)
                throw new IllegalArgumentException("uninitMap cannot be null");
            
            return getUninitInstance(uninitMap, type.regTypeToUninitIndex());
        } else {
            return type.classObject;
        }
    }

}
